package two.chapter_4.c4_1;

import two.chapter_1.c1_3.LinkStack;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;
import two.chapter_1.c1_3.Stack;

public class BreadthFirstPaths implements Paths {
    private boolean marked[];
    private int[] edgeTo;
    private int s;//起点
    public BreadthFirstPaths(Graph g,int s){
        this.s=s;
        marked=new boolean[g.v()];
        edgeTo=new int[g.v()];

        bfs(g,s);
    }

    private void bfs(Graph g,int s) {
        Queue<Integer> queue=new LinkedQueue<>();
        queue.enqueue(s);
        marked[s]=true;
        while (!queue.isEmpty()) {
            int v=queue.dequeue();
            for (int w : g.adj(v)) {
                if (!marked[w]) {
                    queue.enqueue(w);
                    edgeTo[w] = v;
                    marked[w]=true;
                }
            }
        }
    }

    @Override
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))return null;
        Stack<Integer> stack=new LinkStack<>();
        for (int w=v;w!=s;w=edgeTo[w]){
            stack.push(w);
        }
        stack.push(s);
        return stack;
    }
}
